//
// Created by francklinson on 2021/5/29.
//
// BST的插入操作
#include <iostream>

using namespace std;

//Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *insertIntoBST(TreeNode *root, int val) {
        TreeNode *father = nullptr;
        TreeNode *node = root;
        while (node != nullptr) {
            father = node;
            if (val > node->val) node = node->right;
            else node = node->left;
        }
        if (father == nullptr) {
            node = new TreeNode(val);
            return node;
        }
        if (val > father->val) father->right = new TreeNode(val);
        else father->left = new TreeNode(val);
        return root;
    }
};

class Solution2 {
public:
    TreeNode *insertIntoBST(TreeNode *root, int val) {
        if (root == nullptr) {
            return new TreeNode(val);
        }
        TreeNode *pos = root;
        while (pos != nullptr) {
            if (val < pos->val) {
                if (pos->left == nullptr) {
                    pos->left = new TreeNode(val);
                    break;
                } else {
                    pos = pos->left;
                }
            } else {
                if (pos->right == nullptr) {
                    pos->right = new TreeNode(val);
                    break;
                } else {
                    pos = pos->right;
                }
            }
        }
        return root;
    }
};


int main() {
    auto n1 = TreeNode(4), n2 = TreeNode(2), n3 = TreeNode(7), n4 = TreeNode(1), n5 = TreeNode(3);
    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    Solution sol;
    sol.insertIntoBST(&n1, 5);
    return 0;

}